Not to be confused with convex hull, the convex hull trick is a dynamic programming optimization technique. It can be thought of as a data structure supporting the following operations:

• Insert(ax+b): insert the line $ax+b$ into the data structure
• GetMin(x): considering all the lines that have been inserted so far, return the one that has the minimum value at $x$

Applicability

The convex hull trick applies when the dynamic programming recurrence is approximately of the form $$ \mathrm{dp}[i] = \min_{j<i} \left{\mathrm{dp}[j] + b[j]\times a[i]\right}. $$ where $b[j]\geq b[j+1]$ and $a[i] \leq a[i+1]$. The naive way of computing this recurrence with dynamic programming takes $O(n^2)$ time, but only takes $O(n)$ time with the convex hull trick. The restrictions on $a$ and $b$ can be dropped at the expense of a more complex and slightly slower approach.

TODO: Talk about dynamic vs. static variants

Sometimes the above form appears within a more complex recurrence, as is the case for $$ \mathrm{dp}[k][i] = \min_{j<i} \left{\mathrm{dp}[k-1][j] + b[j]\times a[i]\right}. $$ The approach remains very similar, and in this case the convex hull trick brings the time complexity down to $O(kn)$ from $O(kn^2)$. This latter form can also be computed quickly using the divide and conquer optimization

Problems

• Commando
• Land Acquisition
• Batch Scheduling
• Covered Walkway
• Branch Assignment
• Good Inflation
• Cats Transport¹
• Cow School²
• Kalila and Dimna in the Logging Industry³
• Leaves
• Squared Ends

See also

• Dynamic programming optimization

External links

• Convex hull trick
• Effective Usage of C++ STL for quick and concise code writing in competitive programming
• Advanced dynamic programming techniques